package com.leetcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 这是一类问题，可以采用回溯加剪枝的方法，对应这种问题，后期可以改为动态规划解决
 */
public class Leetcode39 {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> outer = new ArrayList<>();
        if (candidates == null)
            return outer;
        List<Integer> inner = new ArrayList<>();
        Arrays.sort(candidates);
        backtrace(outer, inner, candidates, 0, target);
        return outer;
    }

    private void backtrace(List<List<Integer>> outer, List<Integer> inner,
                           int[] candidates,int index, int target) {
        if (target == 0) {
            outer.add(new ArrayList<>(inner));
            return;
        }

        for (int i = index; i < candidates.length && target - candidates[i] >= 0 ; i++) {
            inner.add(candidates[i]);
            backtrace(outer, inner, candidates, i, target - candidates[i]);
            inner.remove(inner.size() - 1);
        }
    }

    public static void main(String[] args) {

    }

}
